package lru

import "container/list"

/**
最近最少使用，相对于仅考虑时间因素的 FIFO 和仅考虑访问频率的 LFU，
LRU 算法可以认为是相对平衡的一种淘汰算法。LRU 认为，
如果数据最近被访问过，那么将来被访问的概率也会更高。
LRU 算法的实现非常简单，维护一个队列，如果某条记录被访问了，
则移动到队尾，那么队首则是最近最少访问的数据，淘汰该条记录即可。
*/

//  为了通用性，允许值是实现了Value接口的任意类型，
//  该接口只包含了一个方法len，用来返回所占内存的大小
type Value interface {
	Len() int
}

// 双向链表节点的数据类型，在链表中仍保存每个值对应的key的好处在于，
// 淘汰首节点时，需要用key从字典中删除对应的映射
type entry struct {
	key   string
	value Value
}

type Cache struct {
	maxBytes  int64      // 允许使用的最大内存
	nbytes    int64      // 当前已使用的内存
	ll        *list.List // 双向链表
	cache     map[string]*list.Element
	onEvicted func(key string, value Value) //某条记录被移除时的回调函数，可以为nil
}

// 方便实例化Cache
func New(maxBytes int64, onEvicted func(string, Value)) *Cache {
	return &Cache{
		maxBytes:  maxBytes,
		ll:        list.New(),
		cache:     make(map[string]*list.Element),
		onEvicted: onEvicted,
	}
}

/**
查找功能
1、从字典中找到对应的双线链表的节点，
2、将该节点移动到队尾
*/
func (c *Cache) Get(key string) (value Value, ok bool) {
	if ele, ok := c.cache[key]; ok {
		//队首队尾是相对的，在这里约定 front 为队尾
		c.ll.MoveToFront(ele)
		//查找返回的值
		kv := ele.Value.(*entry)
		return kv.value, true
	}
	return
}

/**
删除功能——缓存淘汰
移除最近最少访问的节点（队首）
*/
func (c *Cache) RemoveOldest() {
	ele := c.ll.Back()
	if ele != nil {
		// 取到队首节点，从链表中删除
		c.ll.Remove(ele)
		kv := ele.Value.(*entry)
		// 从字典中 c.cache 删除该节点的映射关系
		delete(c.cache, kv.key)
		// 更新当前所用的内存
		c.nbytes -= int64(len(kv.key)) + int64(kv.value.Len())
		if c.onEvicted != nil {
			// 调用回调函数
			c.onEvicted(kv.key, kv.value)
		}
	}
}

/**
save of update
*/

func (c *Cache) AddOrUpdate(key string, value Value) {
	// 存在就更新，否则新增
	if ele, ok := c.cache[key]; ok {
		c.ll.MoveToFront(ele)
		kv := ele.Value.(*entry)
		c.nbytes += int64(len(kv.key)) - int64(kv.value.Len())
		kv.value = value
	} else {
		ele := c.ll.PushFront(&entry{key, value})
		c.cache[key] = ele
		c.nbytes += int64(len(key)) + int64(value.Len())
	}
	//超出内存，淘汰
	for c.maxBytes != 0 && c.maxBytes < c.nbytes {
		c.RemoveOldest()
	}
}

func (c *Cache) Len() int {
	return c.ll.Len()
}
